package open.douban.hashtree;

import java.io.BufferedInputStream;
import java.io.BufferedOutputStream;
import java.io.DataInputStream;
import java.io.DataOutputStream;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileOutputStream;
import java.io.IOException;

/**
 * a hash tree similar to beansdb:
 * http://code.google.com/p/beansdb/source/browse/trunk/htree.c
 * ----------------------- 0(root) <br>
 *---------------------- 1 ... 16 <br>
 *--------------------- 17 ... <br>
 *-------------------- 289 ... <br>
 *------------------- 4913 ... <br>
 *------------------ 83521 ... <br>
 *----------------- 1419857 ... <br>
 *---------------- 24137569 ... <br>
 *--------------- 410338673 ... 4294967296 <br>
 */
public abstract class HashTree {

	public final static int g_index[] = { 0, 1, 17, 289, 4913, 83521, 1419857,
			24137569, 410338673 };
	// limit the height to avoid out of memory
	// otherwise we can not use array to store all the node in memory.
	public final static int MAX_HEIGHT = 6;
	public final static int MAX_ITEM_PER_NODE = 1 << 4 * (8 - MAX_HEIGHT);
	public final static int ITEM_ALLOCATE = 16;
	private final static int[] NUM_OF_MUTEX = new int[16];

	static {
		NUM_OF_MUTEX[0] = 1;
		for (int i = 1; i < 16; i++)
			NUM_OF_MUTEX[i] = NUM_OF_MUTEX[i - 1] * 97;
	}

	protected int height = 0; // tree height, always MAX_HEIGHT here
	protected Node root = null;

	protected String path = null;

	private boolean bigEndian = true;

	public HashTree(String path, boolean bigEndian) throws IOException {
		this.path = path;

		height = 0;
		this.bigEndian = bigEndian;
	}

	protected void build() throws IOException {
		root = createNode(0); // root

		File f = new File(path);
		if (f.exists()) {
			load();
		}
	}

	/* *********************************************************
	 * 
	 * Inner class
	 * 
	 * *******************************************************
	 */
	public static class Item {
		int key; // track_id
		int hash_v; // gps number of a track_id in a given day
	}

	public static class Node {
		boolean isLeaf = false;
		int id = -1; // id in tree
		int height = 0; // node height in tree
		Item[] items = null;
		int item_cnt = 0;
		int hash_v = 0;
	}

	public interface BSTIterator {
		public boolean hasNext();

		public Node next();
	}

	/* *********************************************************
	 * 
	 * File operation
	 * 
	 * *******************************************************
	 */
	/**
	 * save into disk : save Item one by one. Do not provide save/remove API for
	 * single item, for it may be need a key/value system like tc or a quard
	 * tree file to save all the node.
	 */
	public void save() throws IOException {
		// 1) use a temp file and rename the file
		// 2) use FileChannel
		final DataOutputStream out = new DataOutputStream(
				new BufferedOutputStream(new FileOutputStream(path)));
		BSTIterator it = this.iterator();
		while (it.hasNext()) {
			Node n = it.next();
			if (n != null && n.isLeaf) {
				Item[] items = n.items;
				for (int i = 0; i < n.item_cnt; i++) {
					out.writeInt(items[i].key);
					out.writeInt(items[i].hash_v);
				}
			}
		}

		out.flush();
		out.close();
	}

	/**
	 * load from disk : read all the Item into memory. construct tree.
	 */
	public void load() throws IOException {
		DataInputStream input = new DataInputStream(new BufferedInputStream(
				new FileInputStream(path)));
		File f = new File(path);
		int num = (int) (f.length() / 8);
		for (int i = 0; i < num; i++) {
			int key = input.readInt();
			int hash_v = input.readInt();
			this.setItem(key, hash_v, false);
		}
	}

	/* *********************************************************
	 * 
	 * Item operation
	 * 
	 * *******************************************************
	 */
	/**
	 * 
	 * @param key
	 * @param hash_v
	 */
	public void setItem(int key, int hash_v, boolean auto_save)
			throws IOException {
		Item item = new Item();
		item.key = key;
		item.hash_v = hash_v;

		// use recursion instead of find and add
		Node leaf = findLeaf(key);
		setItem(leaf, item, auto_save, true);
	}

	private void setItem(Node leaf, Item item, boolean auto_save, boolean update)
			throws IOException {
		int i = binarySearch(leaf.items, leaf.item_cnt, item.key);

		int h = 0;
		if (i != -1) { // exist key
			h = item.key * item.hash_v - leaf.items[i].key
					* leaf.items[i].hash_v;
			leaf.hash_v += h;
			leaf.items[i].hash_v = item.hash_v;

			if (update)
				updateParent(leaf, 0, h);
		} else { // new key
			leaf.items = insertSort(leaf.items, leaf.item_cnt, item);

			h = item.key * item.hash_v;
			leaf.item_cnt++;
			leaf.hash_v += h;

			if (update)
				updateParent(leaf, 1, h);

			if (leaf.item_cnt > MAX_ITEM_PER_NODE)
				split(leaf);
		}

		if (auto_save)
			save();
	}

	public Item findItem(int key) {
		Node leaf = findLeaf(key);
		if (leaf.item_cnt == 0)
			return null;
		int i = binarySearch(leaf.items, leaf.item_cnt, key);
		return i != -1 ? leaf.items[i] : null;
	}

	/**
	 * never used.
	 * 
	 * @param key
	 */
	public void removeItem(int key, boolean auto_save) throws IOException {
		// use recursion instead of find and remove
		Node leaf = findLeaf(key);
		if (leaf.items == null)
			return;
		int i = binarySearch(leaf.items, leaf.item_cnt, key);
		if (i != -1) {
			int h = leaf.items[i].key * leaf.items[i].hash_v;
			leaf.item_cnt--;
			leaf.hash_v -= h;

			for (int j = i; j < leaf.item_cnt; j++)
				leaf.items[j] = leaf.items[j + 1];

			updateParent(leaf, -1, -h);

			if (leaf != root) {
				Node parent = getParent(leaf);
				if (parent.item_cnt <= MAX_ITEM_PER_NODE)
					merge(parent);
			}
		}

		if (auto_save)
			save();
	}

	private Item[] insertSort(Item[] items, int length, Item item) {
		// enlarge the item array when the array is full
		if (items == null || length == items.length) {
			Item[] temp = new Item[length + ITEM_ALLOCATE];
			if (items != null)
				System.arraycopy(items, 0, temp, 0, length);
			items = temp;
		}

		// find position
		int i = length - 1;
		while (i >= 0 && items[i].key > item.key) {
			items[i + 1] = items[i];
			i--;
		}

		items[i + 1] = item;
		return items;
	}

	/**
	 * @param items
	 * @param length
	 * @param key
	 * @return index in item, -1 if not found
	 */
	private int binarySearch(Item[] items, int length, int key) {
		int l = 0, h = length - 1;
		while (l <= h) {
			int m = (l + h) / 2;
			if (items[m].key == key)
				return m;
			else if (items[m].key < key)
				l = m + 1;
			else
				h = m - 1;
		}

		return -1;
	}

	/**
	 * findLeaf && updateParent is double cost. If we can update parent in
	 * finding leaf, then we can speed up by 1x.
	 * 
	 * @param n
	 * @param delta
	 * @throws IOException
	 */
	private void updateParent(Node n, int item_delta, int hash_delta)
			throws IOException {
		Node parent = getParent(n);
		if (parent == null)
			return;

		parent.item_cnt += item_delta;
		int idx = n.id - child_id(parent, 0);
		hash_delta = hash_delta * NUM_OF_MUTEX[idx];
		parent.hash_v += hash_delta;

		updateParent(parent, item_delta, hash_delta);
	}

	/* *********************************************************
	 * 
	 * Node operation
	 * 
	 * *******************************************************
	 */
	public final static int hex2int(char b) {
		if (('0' <= b && b <= '9') || ('a' <= b && b <= 'f')) {
			return (b >= 'a') ? (b - 'a' + 10) : (b - '0');
		} else {
			return -1;
		}
	}

	public final static char[] int2hex = { '0', '1', '2', '3', '4', '5', '6',
			'7', '8', '9', 'a', 'b', 'c', 'd', 'e', 'f' };

	/**
	 * @param dir
	 *            an octal number, each digit represent an index in a layer. E.g
	 *            0x7e, the dir (path in the tree) is: root -> 7 child -> e
	 *            child. In our case, at most 6 octal number. "" means root node
	 *            dir.
	 * @return if a leaf node, list all the items. [key, hash_v].otherwise, list
	 *         all the child node hash value and item count [i, hash_v,
	 *         item_cnt]
	 */
	public static final String BLANK = " ";
	public static final String LINE = "\n";

	public String listDir(String dir) {
		Node n = root;
		for (int i = 0; i < dir.length(); i++) {
			int idx = hex2int(dir.charAt(i));
			if (!n.isLeaf)
				n = this.getChild(n, idx);
		}

		StringBuilder sb = new StringBuilder();
		if (n.isLeaf) {
			for (int i = 0; i < n.item_cnt; i++) {
				Item item = n.items[i];
				sb.append(item.key).append(BLANK);
				sb.append(item.hash_v).append(LINE);
			}
		} else {
			for (int i = 0; i < 16; i++) {
				Node c = this.getChild(n, i);
				sb.append(int2hex[i]).append(BLANK);
				sb.append(c == null ? 0 : c.hash_v).append(BLANK);
				sb.append(c == null ? 0 : c.item_cnt).append(LINE);
			}
		}

		return sb.toString();
	}

	private Node createNode(int id) {
		boolean enlarge = false;
		while (id >= g_index[height + 1]) {
			this.height++;
			enlarge = true;
		}

		assert height <= MAX_HEIGHT : "never enlarge the pool to " + MAX_HEIGHT;
		if (enlarge) {
			enlarge();
		}

		Node n = new Node();
		n.id = id;
		n.isLeaf = true;
		n.item_cnt = 0;

		int i = 1;
		for (; i < g_index.length; i++) {
			if (g_index[i] > id) {
				n.height = i - 1;
				break;
			}
		}

		node(id, n);
		return n;
	}

	/**
	 * 
	 * @param n
	 * @return
	 */
	private Node getParent(Node n) {
		if (n == root)
			return null;

		int parent_id = parent_id(n);

		return node(parent_id);
	}

	private Node getChild(Node n, int i) {
		int child_id = child_id(n, i);
		if (node(child_id) == null) {
			createNode(child_id);
		}

		return node(child_id);
	}

	private int parent_id(Node n) {
		return g_index[n.height - 1] + ((n.id - g_index[n.height] >> 4));
	}

	private int child_id(Node n, int index) {
		int cid = g_index[n.height + 1] + ((n.id - g_index[n.height]) << 4)
				+ index;
		return cid;
	}

	/**
	 * 
	 * @param key
	 * @param n
	 * @return
	 */
	private int index(int key, Node n) {
		// n.height is in [0,7], 8th layer do not have child
		return bigEndian ? 0x0f & (key >> (7 - n.height) * 4)
				: 0x0f & (key >> n.height * 4);
		// use when keys are full distributed
		// return; // use for small key
	}

	private Node findLeaf(int key) {
		Node n = root;
		while (!n.isLeaf) {
			int i = index(key, n);

			n = getChild(n, i);
		}

		return n;
	}

	private void split(Node n) throws IOException {
		assert n.isLeaf : "only leaf node can be split";
		assert n.height < 8 : "inner node height is less than 8";

		n.isLeaf = false;
		Node[] childs = new Node[16];
		int first_child_id = child_id(n, 0);

		for (int i = 0; i < 16; i++) {
			childs[i] = createNode(first_child_id + i);
		}

		int cnt = n.item_cnt;
		for (int i = 0; i < cnt; i++) {
			Item item = n.items[i];
			n.items[i] = null;

			int j = index(item.key, n);
			setItem(childs[j], item, false, false);
		}

		n.items = null;

		int hash_v = calcHash(n);
		updateParent(n, 0, hash_v - n.hash_v);
		n.hash_v = hash_v;
	}

	private int calcHash(Node n) {
		int h = 0;
		if (n.isLeaf) {
			for (int i = 0; i < n.item_cnt; i++) {
				h += n.items[i].key * n.items[i].hash_v;
			}
		} else {
			int first_child_id = child_id(n, 0);
			for (int i = 15; i >= 0; i--) {
				h = h * 97 + node(first_child_id + i).hash_v;
			}
		}

		return h;
	}

	/**
	 * never used in Meas.
	 * 
	 * @param n
	 */
	private void merge(Node n) throws IOException {
		assert !n.isLeaf : "only inner node can be merged";

		int first_child_id = child_id(n, 0);

		n.item_cnt = 0; // re-build
		for (int i = 0; i < 16; i++) {
			Node child = node(first_child_id + i);
			assert child.isLeaf : "only leaf node parent can be merged";
			for (int j = 0; j < child.item_cnt; j++)
				setItem(n, child.items[j], false, false);
			remove(first_child_id + i);
		}

		n.isLeaf = true;

		int hash_v = calcHash(n);
		updateParent(n, 0, hash_v - n.hash_v);
		n.hash_v = hash_v;
	}

	public int getItemNumber() {
		return root.item_cnt;
	}

	/* *********************************************************
	 * 
	 * Node abstract operation dependent on the pool(container) implementation
	 * 
	 * *******************************************************
	 */
	/**
	 * get node
	 * 
	 * @param id
	 * @return
	 */
	abstract protected Node node(int id);

	/**
	 * set node
	 * 
	 * @param id
	 * @param n
	 */
	abstract protected void node(int id, Node n);

	/**
	 * remove node
	 * 
	 * @param id
	 */
	abstract protected void remove(int id);

	/**
	 * tree height increase, enlarge node pool.
	 */
	abstract protected void enlarge();

	/**
	 * init node pool.
	 */
	abstract protected void init();

	/**
	 * @return a breadth first iterator
	 */
	abstract public BSTIterator iterator();

	abstract public int getNodeNumber();
}
